/*
 * Преобразование π-функции в z-функцию
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>

#define MEMDEBUG

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif
#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a)^(b)) && ((b)^=(a)^=(b), (a)^=(b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))
#define MAX(a, b)	((a) > (b) ? (a) : (b))

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0)
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

/* {{{ z-function */
extern unsigned *
z_function(const char *s)
{
	int i, l, r;
	unsigned *z;
	size_t len;

	assert(s != NULL);
	len = strlen(s);
	z = s_calloc(len, sizeof *z);

	for (i = 1, l = 0, r = 0; i < len; ++i) {
		if (i <= r)
			z[i] = MIN(r - i + 1, z[i - l]);
		while (i + z[i] < len && s[z[i]] == s[i + z[i]])
			++z[i];
		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}

	return z;
}
/* }}} */

int *
prefix_to_z_replay(const int *pref, const int len)
{
	register int i, m;
	int *string;
	int chr;
	int *z;
	int l, r;

	/*
	 * restore the string image from the π-function
	 */
	string = s_calloc(len, sizeof *string);
	for (i = 0, chr = 1; i < len; i++)
		if (pref[i] == 0)
			string[i] = chr++;
		else
			string[i] = string[pref[i] - 1];

	/*
	 * calculate z-function of the restored string image
	 */
	z = s_calloc(len, sizeof *z);
	for (l = r = 0, i = 1; i < len; i++) {
		if (i >= r) {
			m = 0;
			while (i + m < len && string[m] == string[i + m])
				m++;
			z[i] = m;
			if (z[i] > 0) {
				r = i + z[i];
				l = i;
			}
		} else if (z[i - l] < r - i) {
			z[i] = z[i - l];
		} else {
			m = 0;
			while (r - i + m < len && r + m < len &&
			       string[r - i + m] == string[r + m])
				m++;
			z[i] = r - i + m;
			r = i + z[i];
			l = i;
		}
	}
	*z = len;

	free(string);
	return z;
}

int *
prefix_to_z(const int *pref, const int len)
{
	int *z;
	register int i;
	int l, r;

	z = s_calloc(len, sizeof *z);
	i = 1;
	while (i < len) {
		if (pref[i])
			z[i - pref[i] + 1] = MAX(z[i - pref[i] + 1], pref[i]);
		i++;
	}

	l = r =  0;
	i = 1;
	while (i < len) {
		if (i + z[i] > r) {
			l = i;
			r = z[i] + i;
		}
		z[i] = MAX(z[i], MIN(z[i - l], r - i));
		i++;
	}
	z[0] = len;

	return z;
}

int
main(int argc, char **argv)
{
	int n, *pref, *z;
	int i;

	scanf("%d", &n);
	pref = s_calloc(n, sizeof *pref);
	for (i = 0; i < n; i++)
		scanf("%d", pref + i);

	z = prefix_to_z(pref, n);
	for (i = 0; i < n; i++)
		printf("%d%c", z[i], i + 1 == n ? '\n' : ' ');

	free(pref);
	free(z);

	return 0;
}
